#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#include "parser.h"

#define RING_SIZE 50
#define frand() ((double) rand() / (RAND_MAX+1.0))
#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )

// Global variables
int DIFF_TOLERANCE;

// Function prototypes
int accept(double T, int cost_diff);
int time_in_seconds();
int time_in_microseconds();

// Structs
struct Move {
  int node_1;
  int node_2;
  struct Move *next_move;
};

struct Move *my_move;
struct Move **last_move;

int main(int argc, char *argv[])
{
  int rank = 0;

  int start_time;
  start_time = time_in_seconds();

  char *input;
  int C, timelimit;
    if (argc != 6) {
      perror("Usage: vlsi <input-filename> -C <C> -timelimit <time-limit>\n");
      return -1;
    }
    else {
      // Parse command line arguments.
      input = argv[1];

      if (!(strcmp(argv[2], "-C"))) {
	sscanf(argv[3], "%d", &C);
      }
      else if (!(strcmp(argv[2], "-timelimit"))) {
	sscanf(argv[3], "%d", &timelimit);
      }
      else {
	perror("Usage: vlsi <input-filename> -C <C> -timelimit <time-limit>\n");
	return -1;
      }

      if (!(strcmp(argv[4], "-C"))) {
	sscanf(argv[5], "%d", &C);
      }
      else if (!(strcmp(argv[4], "-timelimit"))) {
	sscanf(argv[5], "%d", &timelimit);
      }
      else {
	perror("Usage: vlsi <input-filename> -C <C> -timelimit <time-limit>\n");
	return -1;
      }
    }
    
  int sqrt_c = (int)sqrt(C);

  // Algorithm temporary variables
  int cost_diff, final_cost;
  int node_1, node_2, cell_1, cell_2, node_cell, conn_node, conn_cell;
  double T;

  // Algorithm permanent read-only variables
  int **connections_array;
  int *numconn_array;
  int N;

  // Shared algorithm permanent read-only variables
  int **connections_array_shared;
  int *numconn_array_shared;

  int i, j;

  /*
    Processor 0 will do the work of parsing the input file and storing local copies of the permanent
    read-only variables. Then, it will copy those variables to shared memory and let each processor,
   in turn, copy the shared values to their own local storage.
  */
    parse(input, &connections_array, &numconn_array, &N);
    connections_array_shared = malloc(N * sizeof(int *));
    numconn_array_shared = malloc(N * sizeof(int));
    for (i = 0; i < N; i++) {
      numconn_array_shared[i] = numconn_array[i];
      connections_array_shared[i] = malloc(sizeof(int) * numconn_array[i]);
      for (j = 0; j < numconn_array[i]; j++) {
	connections_array_shared[i][j] = connections_array[i][j];
      }
    }

  /*
    Initialize the lock for the move list. This lock is needed to append moves to the
    moves linked list.
  */
    struct Move *prev_move;
    struct Move *curr_move;
    // allocate first move
    my_move = malloc(sizeof(struct Move));
    my_move->node_1 = -1;
    my_move->node_2 = -1;
    prev_move = my_move;
    // allocate rest of ring
    for (i = 1; i < RING_SIZE; i++) {
      curr_move = malloc(sizeof(struct Move));
      curr_move->node_1 = -1;
      curr_move->node_2 = -1;
      prev_move->next_move = curr_move;
      prev_move = curr_move;
    }
    curr_move->next_move = my_move;
    // point last move to my move
    last_move = malloc(sizeof(struct Move *));
    *last_move = my_move;

  /*
    The difference between the maximum number of nodes per cell and the
    minimum number of nodes per cell should not exceed 0.01 x N/C.
  */
  double constraint = max(0.01 * ((double) N)/ C, 1);

  /*
    When calculating acceptance of a state whose cost is higher than the current
    state (positive diff), the temperature is scaled down by a factor of
    1
    ---------------------
    diff
    --------------  +  1
    DIFF_TOLERANCE
  */
  DIFF_TOLERANCE = 2;

  // Seed the random number generator so each processor's seed is unique.
  srand(time_in_seconds() + rank);

  // data structures for the algorithm
  int node_locations[N]; // mapping of cells to nodes

  // find -1 nodes
  int num_middle_nodes = 0;
  for (i = N-1; i >= 0; i--) {
    if (numconn_array_shared[i] == N-1)
      num_middle_nodes++;
    else
      break;
  }

  // generate initial solution
  for (i = 0; i < N; i++) {
    if (i < N - num_middle_nodes) {
      if (i*C/N < C/2)
	node_locations[i] = i*C/N;
      else
	node_locations[i] = (i+num_middle_nodes)*C/N;

    }
    else
      node_locations[i] = C/2;
  }

  final_cost = 0;
  // calculate initial cost for breaking purposes
  for (i = 0; i < N; i++) {
    node_cell = node_locations[i];
    for (j = 0; j < numconn_array_shared[i]; j++) {
      conn_node = connections_array_shared[i][j];
      if (conn_node > i) {
	conn_cell = node_locations[conn_node];
	// Differences in x in new state
	final_cost += abs(node_cell / sqrt_c - conn_cell / sqrt_c);
	// Differences in y in new state
	final_cost += abs((node_cell % sqrt_c) - (conn_cell % sqrt_c));
      }
    }
  }
  
  printf("Initial cost of rank %d: %d\n", rank, final_cost);

  int curr_time;
  while ((curr_time = time_in_seconds() - start_time) < timelimit) {
    // Make sure we are up-to-date
    while (my_move != *last_move) {
      my_move = my_move->next_move;
      cell_1 = node_locations[my_move->node_1];
      cell_2 = node_locations[my_move->node_2];
      node_locations[my_move->node_1] = cell_2;
      node_locations[my_move->node_2] = cell_1;
    }

    T = 1 - ((double)curr_time) / timelimit;

    // Do shit
    node_1 = rand() % N;
    node_2 = rand() % N;

    cell_1 = node_locations[node_1];
    cell_2 = node_locations[node_2];

    // If the change is a no-move, don't accept it. It's stupid.
    if (cell_1 == cell_2)
      continue;

    // Calculate cost diff
    cost_diff = 0;
    // Cost diff due to moving node 1
    for (i = 0; i < numconn_array_shared[node_1]; i++) {
      conn_node = connections_array_shared[node_1][i];
      if (conn_node != node_2) {
	conn_cell = node_locations[conn_node];
	// Differences in x in new state
	cost_diff += abs(cell_2 / sqrt_c - conn_cell / sqrt_c);
	// Differences in y in new state
	cost_diff += abs((cell_2 % sqrt_c) - (conn_cell % sqrt_c));
	// Differences in x in old state
	cost_diff -= abs(cell_1 / sqrt_c - conn_cell / sqrt_c);
	// Differences in y in old state
	cost_diff -= abs((cell_1 % sqrt_c) - (conn_cell % sqrt_c));
      }
    }
    // Cost diff due to moving node 2
    for (i = 0; i < numconn_array_shared[node_2]; i++) {
      conn_node = connections_array_shared[node_2][i];
      if (conn_node != node_1) {
	conn_cell = node_locations[conn_node];
	// Differences in x in new state
	cost_diff += abs(cell_1 / sqrt_c - conn_cell / sqrt_c);
	// Differences in y in new state
	cost_diff += abs((cell_1 % sqrt_c) - (conn_cell % sqrt_c));
	// Differences in x in old state
	cost_diff -= abs(cell_2 / sqrt_c - conn_cell / sqrt_c);
	// Differences in y in old state
	cost_diff -= abs((cell_2 % sqrt_c) - (conn_cell % sqrt_c));
      }
    }

    if (cost_diff <= 0 || accept(T, cost_diff)) {
	/* If my_move has a next move, you can't accept because you need to
	   get back up-to-date. */
	if (my_move == *last_move) {
	  // Make local changes
	  node_locations[node_1] = cell_2;
	  node_locations[node_2] = cell_1;

	  // Share the change
	  my_move = my_move->next_move;
	  my_move->node_1 = node_1;
	  my_move->node_2 = node_2;	  
	  *last_move = my_move;
	}
    }
  }
    while (my_move != *last_move) {
      my_move = my_move->next_move;
      cell_1 = node_locations[my_move->node_1];
      cell_2 = node_locations[my_move->node_2];
      node_locations[my_move->node_1] = cell_2;
      node_locations[my_move->node_2] = cell_1;
    }

    final_cost = 0;
    // calculate initial cost for fun
    for (i = 0; i < N; i++) {
      node_cell = node_locations[i];
      for (j = 0; j < numconn_array_shared[i]; j++) {
	conn_node = connections_array_shared[i][j];
	if (conn_node > i) {
	  conn_cell = node_locations[conn_node];
	  // Differences in x in new state
	  final_cost += abs(node_cell / sqrt_c - conn_cell / sqrt_c);
	  // Differences in y in new state
	  final_cost += abs((node_cell % sqrt_c) - (conn_cell % sqrt_c));
	}
      }
    }

    printf("  Final cost of rank %d: %d\n", rank, final_cost);


  return 0;
}

// Only call this accept() function if the cost c' of the new state is larger
// than the cost of the previous state c, or cost_diff = c' - c > 0
int accept(double T, int cost_diff) {
  double rand_num;
  // Scale the probability based on cost_diff
  T = T * (1 / ((cost_diff / DIFF_TOLERANCE) + 1));
  rand_num = frand();
  return rand_num < T;
}

int time_in_seconds() {
  /* get current time in seconds */
  static struct timeval t;
  gettimeofday(&t,NULL);
  return t.tv_sec;
}

int time_in_microseconds() {
  /* get current time in seconds */
  static struct timeval t;
  gettimeofday(&t,NULL);
  return t.tv_sec *1000000 + t.tv_usec;
}
